class Solution {
 public:
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    int len = nums.size();
    return Create(nums, 0, len - 1);
  }
  TreeNode* Create(vector<int>& nums, int l, int r) {
    if (l > r) return nullptr;
    // int mid = left + ((right - left) / 2);
    int root_index = (l + r) % 2 == 0 ? (l + r) / 2 : (l + r + 1) / 2;
    TreeNode* node = new TreeNode(nums[root_index]);
    node->left = Create(nums, l, root_index - 1);
    node->right = Create(nums, root_index + 1, r);
    return node;
  }
};
// TODO:迭代法